<!-- HTML header for doxygen 1.8.6-->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.13"/>
<title>OpenCV: Harris Corner Detection</title>
<link href="../../opencv.ico" rel="shortcut icon" type="image/x-icon" />
<link href="../../tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="../../jquery.js"></script>
<script type="text/javascript" src="../../dynsections.js"></script>
<script type="text/javascript" src="../../tutorial-utils.js"></script>
<link href="../../search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="../../search/searchdata.js"></script>
<script type="text/javascript" src="../../search/search.js"></script>
<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    extensions: ["tex2jax.js", "TeX/AMSmath.js", "TeX/AMSsymbols.js"],
    jax: ["input/TeX","output/HTML-CSS"],
});
//<![CDATA[
MathJax.Hub.Config(
{
  TeX: {
      Macros: {
          matTT: [ "\\[ \\left|\\begin{array}{ccc} #1 & #2 & #3\\\\ #4 & #5 & #6\\\\ #7 & #8 & #9 \\end{array}\\right| \\]", 9],
          fork: ["\\left\\{ \\begin{array}{l l} #1 & \\mbox{#2}\\\\ #3 & \\mbox{#4}\\\\ \\end{array} \\right.", 4],
          forkthree: ["\\left\\{ \\begin{array}{l l} #1 & \\mbox{#2}\\\\ #3 & \\mbox{#4}\\\\ #5 & \\mbox{#6}\\\\ \\end{array} \\right.", 6],
          forkfour: ["\\left\\{ \\begin{array}{l l} #1 & \\mbox{#2}\\\\ #3 & \\mbox{#4}\\\\ #5 & \\mbox{#6}\\\\ #7 & \\mbox{#8}\\\\ \\end{array} \\right.", 8],
          vecthree: ["\\begin{bmatrix} #1\\\\ #2\\\\ #3 \\end{bmatrix}", 3],
          vecthreethree: ["\\begin{bmatrix} #1 & #2 & #3\\\\ #4 & #5 & #6\\\\ #7 & #8 & #9 \\end{bmatrix}", 9],
          cameramatrix: ["#1 = \\begin{bmatrix} f_x & 0 & c_x\\\\ 0 & f_y & c_y\\\\ 0 & 0 & 1 \\end{bmatrix}", 1],
          distcoeffs: ["(k_1, k_2, p_1, p_2[, k_3[, k_4, k_5, k_6 [, s_1, s_2, s_3, s_4[, \\tau_x, \\tau_y]]]]) \\text{ of 4, 5, 8, 12 or 14 elements}"],
          distcoeffsfisheye: ["(k_1, k_2, k_3, k_4)"],
          hdotsfor: ["\\dots", 1],
          mathbbm: ["\\mathbb{#1}", 1],
          bordermatrix: ["\\matrix{#1}", 1]
      }
  }
}
);
//]]>
</script><script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js"></script>
<link href="../../doxygen.css" rel="stylesheet" type="text/css" />
<link href="../../stylesheet.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<!--#include virtual="/google-search.html"-->
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectlogo"><img alt="Logo" src="../../opencv-logo-small.png"/></td>
  <td style="padding-left: 0.5em;">
   <div id="projectname">OpenCV
   &#160;<span id="projectnumber">4.5.2</span>
   </div>
   <div id="projectbrief">Open Source Computer Vision</div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.13 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "../../search",false,'Search');
</script>
<script type="text/javascript" src="../../menudata.js"></script>
<script type="text/javascript" src="../../menu.js"></script>
<script type="text/javascript">
$(function() {
  initMenu('../../',true,false,'search.php','Search');
  $(document).ready(function() { init_search(); });
});
</script>
<div id="main-nav"></div>
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div id="nav-path" class="navpath">
  <ul>
<li class="navelem"><a class="el" href="../../d6/d00/tutorial_py_root.html">OpenCV-Python Tutorials</a></li><li class="navelem"><a class="el" href="../../db/d27/tutorial_py_table_of_contents_feature2d.html">Feature Detection and Description</a></li>  </ul>
</div>
</div><!-- top -->
<div class="header">
  <div class="headertitle">
<div class="title">Harris Corner Detection </div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><h2>Goal </h2>
<p>In this chapter,</p>
<ul>
<li>We will understand the concepts behind Harris Corner Detection.</li>
<li>We will see the following functions: <b><a class="el" href="../../dd/d1a/group__imgproc__feature.html#gac1fc3598018010880e370e2f709b4345" title="Harris corner detector. ">cv.cornerHarris()</a></b>, <b><a class="el" href="../../dd/d1a/group__imgproc__feature.html#ga354e0d7c86d0d9da75de9b9701a9a87e" title="Refines the corner locations. ">cv.cornerSubPix()</a></b></li>
</ul>
<h2>Theory </h2>
<p>In the last chapter, we saw that corners are regions in the image with large variation in intensity in all the directions. One early attempt to find these corners was done by <b>Chris Harris &amp; Mike Stephens</b> in their paper <b>A Combined Corner and Edge Detector</b> in 1988, so now it is called the Harris Corner Detector. He took this simple idea to a mathematical form. It basically finds the difference in intensity for a displacement of \((u,v)\) in all directions. This is expressed as below:</p>
<p class="formulaDsp">
\[E(u,v) = \sum_{x,y} \underbrace{w(x,y)}_\text{window function} \, [\underbrace{I(x+u,y+v)}_\text{shifted intensity}-\underbrace{I(x,y)}_\text{intensity}]^2\]
</p>
<p>The window function is either a rectangular window or a Gaussian window which gives weights to pixels underneath.</p>
<p>We have to maximize this function \(E(u,v)\) for corner detection. That means we have to maximize the second term. Applying Taylor Expansion to the above equation and using some mathematical steps (please refer to any standard text books you like for full derivation), we get the final equation as:</p>
<p class="formulaDsp">
\[E(u,v) \approx \begin{bmatrix} u &amp; v \end{bmatrix} M \begin{bmatrix} u \\ v \end{bmatrix}\]
</p>
<p>where</p>
<p class="formulaDsp">
\[M = \sum_{x,y} w(x,y) \begin{bmatrix}I_x I_x &amp; I_x I_y \\ I_x I_y &amp; I_y I_y \end{bmatrix}\]
</p>
<p>Here, \(I_x\) and \(I_y\) are image derivatives in x and y directions respectively. (These can be easily found using <b><a class="el" href="../../d4/d86/group__imgproc__filter.html#gacea54f142e81b6758cb6f375ce782c8d" title="Calculates the first, second, third, or mixed image derivatives using an extended Sobel operator...">cv.Sobel()</a></b>).</p>
<p>Then comes the main part. After this, they created a score, basically an equation, which determines if a window can contain a corner or not.</p>
<p class="formulaDsp">
\[R = det(M) - k(trace(M))^2\]
</p>
<p>where</p><ul>
<li>\(det(M) = \lambda_1 \lambda_2\)</li>
<li>\(trace(M) = \lambda_1 + \lambda_2\)</li>
<li>\(\lambda_1\) and \(\lambda_2\) are the eigenvalues of M</li>
</ul>
<p>So the magnitudes of these eigenvalues decide whether a region is a corner, an edge, or flat.</p>
<ul>
<li>When \(|R|\) is small, which happens when \(\lambda_1\) and \(\lambda_2\) are small, the region is flat.</li>
<li>When \(R&lt;0\), which happens when \(\lambda_1 &gt;&gt; \lambda_2\) or vice versa, the region is edge.</li>
<li>When \(R\) is large, which happens when \(\lambda_1\) and \(\lambda_2\) are large and \(\lambda_1 \sim \lambda_2\), the region is a corner.</li>
</ul>
<p>It can be represented in a nice picture as follows:</p>
<div class="image">
<img src="../../harris_region.jpg" alt="harris_region.jpg"/>
<div class="caption">
image</div></div>
<p> So the result of Harris Corner Detection is a grayscale image with these scores. Thresholding for a suitable score gives you the corners in the image. We will do it with a simple image.</p>
<h2>Harris Corner Detector in OpenCV </h2>
<p>OpenCV has the function <b><a class="el" href="../../dd/d1a/group__imgproc__feature.html#gac1fc3598018010880e370e2f709b4345" title="Harris corner detector. ">cv.cornerHarris()</a></b> for this purpose. Its arguments are:</p>
<ul>
<li><b>img</b> - Input image. It should be grayscale and float32 type.</li>
<li><b>blockSize</b> - It is the size of neighbourhood considered for corner detection</li>
<li><b>ksize</b> - Aperture parameter of the Sobel derivative used.</li>
<li><b>k</b> - Harris detector free parameter in the equation.</li>
</ul>
<p>See the example below: </p><div class="fragment"><div class="line"><span class="keyword">import</span> numpy <span class="keyword">as</span> np</div><div class="line"><span class="keyword">import</span> cv2 <span class="keyword">as</span> cv</div><div class="line"></div><div class="line">filename = <span class="stringliteral">&#39;chessboard.png&#39;</span></div><div class="line">img = <a class="code" href="../../d4/da8/group__imgcodecs.html#ga288b8b3da0892bd651fce07b3bbd3a56">cv.imread</a>(filename)</div><div class="line">gray = <a class="code" href="../../d8/d01/group__imgproc__color__conversions.html#ga397ae87e1288a81d2363b61574eb8cab">cv.cvtColor</a>(img,cv.COLOR_BGR2GRAY)</div><div class="line"></div><div class="line">gray = np.float32(gray)</div><div class="line">dst = <a class="code" href="../../dd/d1a/group__imgproc__feature.html#gac1fc3598018010880e370e2f709b4345">cv.cornerHarris</a>(gray,2,3,0.04)</div><div class="line"></div><div class="line"><span class="comment">#result is dilated for marking the corners, not important</span></div><div class="line">dst = <a class="code" href="../../d4/d86/group__imgproc__filter.html#ga4ff0f3318642c4f469d0e11f242f3b6c">cv.dilate</a>(dst,<span class="keywordtype">None</span>)</div><div class="line"></div><div class="line"><span class="comment"># Threshold for an optimal value, it may vary depending on the image.</span></div><div class="line">img[dst&gt;0.01*dst.max()]=[0,0,255]</div><div class="line"></div><div class="line"><a class="code" href="../../df/d24/group__highgui__opengl.html#gaae7e90aa3415c68dba22a5ff2cefc25d">cv.imshow</a>(<span class="stringliteral">&#39;dst&#39;</span>,img)</div><div class="line"><span class="keywordflow">if</span> <a class="code" href="../../d7/dfc/group__highgui.html#ga5628525ad33f52eab17feebcfba38bd7">cv.waitKey</a>(0) &amp; 0xff == 27:</div><div class="line">    <a class="code" href="../../d7/dfc/group__highgui.html#ga6b7fc1c1a8960438156912027b38f481">cv.destroyAllWindows</a>()</div></div><!-- fragment --><p> Below are the three results:</p>
<div class="image">
<img src="../../harris_result.jpg" alt="harris_result.jpg"/>
<div class="caption">
image</div></div>
 <h2>Corner with SubPixel Accuracy </h2>
<p>Sometimes, you may need to find the corners with maximum accuracy. OpenCV comes with a function <b><a class="el" href="../../dd/d1a/group__imgproc__feature.html#ga354e0d7c86d0d9da75de9b9701a9a87e" title="Refines the corner locations. ">cv.cornerSubPix()</a></b> which further refines the corners detected with sub-pixel accuracy. Below is an example. As usual, we need to find the Harris corners first. Then we pass the centroids of these corners (There may be a bunch of pixels at a corner, we take their centroid) to refine them. Harris corners are marked in red pixels and refined corners are marked in green pixels. For this function, we have to define the criteria when to stop the iteration. We stop it after a specified number of iterations or a certain accuracy is achieved, whichever occurs first. We also need to define the size of the neighbourhood it searches for corners. </p><div class="fragment"><div class="line"><span class="keyword">import</span> numpy <span class="keyword">as</span> np</div><div class="line"><span class="keyword">import</span> cv2 <span class="keyword">as</span> cv</div><div class="line"></div><div class="line">filename = <span class="stringliteral">&#39;chessboard2.jpg&#39;</span></div><div class="line">img = <a class="code" href="../../d4/da8/group__imgcodecs.html#ga288b8b3da0892bd651fce07b3bbd3a56">cv.imread</a>(filename)</div><div class="line">gray = <a class="code" href="../../d8/d01/group__imgproc__color__conversions.html#ga397ae87e1288a81d2363b61574eb8cab">cv.cvtColor</a>(img,cv.COLOR_BGR2GRAY)</div><div class="line"></div><div class="line"><span class="comment"># find Harris corners</span></div><div class="line">gray = np.float32(gray)</div><div class="line">dst = <a class="code" href="../../dd/d1a/group__imgproc__feature.html#gac1fc3598018010880e370e2f709b4345">cv.cornerHarris</a>(gray,2,3,0.04)</div><div class="line">dst = <a class="code" href="../../d4/d86/group__imgproc__filter.html#ga4ff0f3318642c4f469d0e11f242f3b6c">cv.dilate</a>(dst,<span class="keywordtype">None</span>)</div><div class="line">ret, dst = <a class="code" href="../../d7/d1b/group__imgproc__misc.html#gae8a4a146d1ca78c626a53577199e9c57">cv.threshold</a>(dst,0.01*dst.max(),255,0)</div><div class="line">dst = np.uint8(dst)</div><div class="line"></div><div class="line"><span class="comment"># find centroids</span></div><div class="line">ret, labels, stats, centroids = <a class="code" href="../../d3/dc0/group__imgproc__shape.html#gae57b028a2b2ca327227c2399a9d53241">cv.connectedComponentsWithStats</a>(dst)</div><div class="line"></div><div class="line"><span class="comment"># define the criteria to stop and refine the corners</span></div><div class="line">criteria = (cv.TERM_CRITERIA_EPS + cv.TERM_CRITERIA_MAX_ITER, 100, 0.001)</div><div class="line">corners = <a class="code" href="../../dd/d1a/group__imgproc__feature.html#ga354e0d7c86d0d9da75de9b9701a9a87e">cv.cornerSubPix</a>(gray,np.float32(centroids),(5,5),(-1,-1),criteria)</div><div class="line"></div><div class="line"><span class="comment"># Now draw them</span></div><div class="line">res = np.hstack((centroids,corners))</div><div class="line">res = np.int0(res)</div><div class="line">img[res[:,1],res[:,0]]=[0,0,255]</div><div class="line">img[res[:,3],res[:,2]] = [0,255,0]</div><div class="line"></div><div class="line"><a class="code" href="../../d4/da8/group__imgcodecs.html#gabbc7ef1aa2edfaa87772f1202d67e0ce">cv.imwrite</a>(<span class="stringliteral">&#39;subpixel5.png&#39;</span>,img)</div></div><!-- fragment --><p> Below is the result, where some important locations are shown in the zoomed window to visualize:</p>
<div class="image">
<img src="../../subpixel3.png" alt="subpixel3.png"/>
<div class="caption">
image</div></div>
 <h2>Additional Resources </h2>
<h2>Exercises </h2>
</div></div><!-- contents -->
<!-- HTML footer for doxygen 1.8.6-->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated on Fri Apr 2 2021 11:36:37 for OpenCV by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="../../doxygen.png" alt="doxygen"/>
</a> 1.8.13
</small></address>
<script type="text/javascript">
//<![CDATA[
addTutorialsButtons();
//]]>
</script>
</body>
</html>
